/*
 * @lc app=leetcode.cn id=572 lang=cpp
 *
 * [572] 另一个树的子树
 * 问题某子树是否是主树的子结构
 * 方法：前序遍历的递归方法
 */

// @lc code=start
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
 public:
  bool isSubtree(TreeNode* s, TreeNode* t)  // 遍历主树s(前序遍历递归法)
  {
    if (nullptr == s)
      return false;  // 前序遍历递归的出口，注意一定要加判断空指针的语句，后面有s->left和s->right

    // 前序遍历（递归法）主树t各结点,从根结点到左子树再到右子树（s一直在延伸，展开分支）
    if (isSame(s, t))  // 判断当前结点下的子树是否一样
      return true;
    else  // 判断当前结点的左子树是否为子树t,再判断右子树是否为子树t
    {
      return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
  }

 private:
  // 确定s父结点后，开始同时扫描（递归法）s和t，看是各个结点是否相等
  bool isSame(TreeNode* s, TreeNode* t)
  {
    if (nullptr == s && nullptr == t)
      return true;  // 如果最后均遍历到空结点，返回true
    else if (nullptr == s || nullptr == t)
      return false;  // 如果一个遍历到空，一个没有，说明不同，返回false

    if (s->val == t->val)
    {
      return isSame(s->left, t->left) && isSame(s->right, t->right);
    }
    else
      return false;  // 不相同返回假
  }
};
// @lc code=end
